class code3 {
    //快速选择算法
    public int findKthLargest(int[] nums, int k) {
        int key = qsort(nums,k,0,nums.length-1);
        return key;
    }
    public int qsort(int[] nums,int k,int l,int r) {
        if(l==r) return nums[l];

        int left=l-1,right=r+1,i=l;
        int key = nums[l+new Random().nextInt(r-l+1)];
        while(i<right) {
            if(nums[i]<key) swap(nums,++left,i++);
            else if(nums[i]==key) i++;
            else swap(nums,--right,i);
        }

        //2.分类讨论
        int b = right-left-1,c = r-right+1;
        if(c>=k) return qsort(nums,k,right,r);
        else if(b+c>=k) return key;
        else return qsort(nums,k-b-c,l,left);
    }
    public void swap(int[] nums,int a,int b) {
        int tmp = nums[a];
        nums[a] = nums[b];
        nums[b] = tmp;
    }
}